package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import data_structure.BTNode;

public class LeetCode_day12_tree {
	
	/**
	 * ! Given a binary tree, return the zigzag level order traversal of its nodes' values. 
	 * (ie, from left to right, then right to left for the next level and alternate between).
	 * @param root
	 */
	public static void zigzagLevelOrderTraversalBT(BTNode root){
		if(root == null) return;
		Stack<BTNode> qforward = new Stack<BTNode>();
		Queue<BTNode> qbackward = new LinkedList<BTNode>();
		qforward.push(root);//first level
		boolean flag = true;
		
		while(!qforward.isEmpty() || !qbackward.isEmpty()){
			BTNode node = null;
			boolean newFlag = flag;
			while(!qforward.isEmpty()){
				newFlag = true;
				node = qforward.pop();
				if(node.left != null) qbackward.offer(node.left);
				if(node.right != null) qbackward.offer(node.right);
				if(flag != newFlag){
					System.out.println();
					flag = newFlag;
				}
				if(node != null)
					System.out.print(node.val + " ");
			}
			while(!qbackward.isEmpty()){
				newFlag = false;
				node = qbackward.poll();
				if(node.left != null) qforward.push(node.left);
				if(node.right != null) qforward.push(node.right);
				if(flag != newFlag){
					System.out.println();
					flag = newFlag;
				}
				if(node != null)
					System.out.print(node.val + " ");
			}
		}
	}
	
	/**
	 * Given a binary tree, return the bottom-up level order traversal of its nodes' values. 
	 * (ie, from left to right, level by level from leaf to root).
	 * @param root
	 */
	public static void binaryTreeLevelOrderTraversalII(BTNode root){
		if(root == null) return;
		BTNode ind = root;
		List<BTNode> q = new ArrayList<BTNode>();
		q.add(root);
		q.add(new BTNode(null));//end of the first level
		
		for(int i = 0 ; i < q.size() ; i++){
			BTNode node = q.get(i);
			if(node.val != null){//same level
				if(node.left != null)  q.add(node.left);
				if(node.right != null) q.add(node.right);
			}else 
				if(i > 0 && q.get(i-1).val != null)
					q.add(new BTNode(null));
		}
		
		for(int i = q.size()-1 ; i> -1 ; i--){
			BTNode node = q.get(i);
			if(node.val != null) System.out.print(node.val + " ");
			else System.out.println();
		}
		
	}
	
	public static BTNode convertSortedArrayToBalancedBST(int[] a, int start, int end){
		if(a == null) return null;
		if(start > end) return null;
		int mid = start + (end - start) / 2;
		BTNode<Number> node = new BTNode(a[mid]);
		node.left = convertSortedArrayToBalancedBST(a, start, mid-1);
		node.right = convertSortedArrayToBalancedBST(a, mid+1, end);
		return node;
	}
	
	/**
	 * !
	 * @param iter
	 * @return
	 */
	public static BTNode convertSortedLinkedListToBalancedBST(Iterator<Integer> iter){
		if(iter == null || !iter.hasNext()) return null;
		BTNode node = new BTNode();
		node.left = convertSortedLinkedListToBalancedBST(iter);
		node.val = iter.next();
		node.right = convertSortedLinkedListToBalancedBST(iter);
		return node;
	}
	
	/**
	 * Given a binary tree, determine if it is height-balanced.
	 * For this problem, a height-balanced binary tree 
	 * is defined as a binary tree in which the depth of the two subtrees 
	 * of every node never differ by more than 1.
	 * 
	 * Binary tree is balanced <- left is balanced && right is balanced && |depth of left - depth of right| <= 1
	 * @param root
	 * @return
	 */
	public static boolean balancedBT(BTNode root){
		if(root == null) return true;
		int height1 = findHeightOfTree(root.left);
		int height2 = findHeightOfTree(root.right);
		return balancedBT(root.left) && balancedBT(root.right) && Math.abs(height1 - height2) <= 1;
	}
	
	public static <T> int findHeightOfTree(BTNode root){
		if(root == null) return 0;
		int height = 1;
		if(root.left != null || root.right != null){
			PriorityQueue<Integer> heights = new PriorityQueue<Integer>(2, new Comparator<Integer>(){
				@Override
				public int compare(Integer o1, Integer o2) {
					if(o1 > o2) return -1;
					if(o1 < o2) return 1;
					return 0;
				}
			});
			heights.add(findHeightOfTree(root.left));
			heights.add(findHeightOfTree(root.right));
			height += (int)heights.peek();
		}
		return height;
	}//*/
	
	/**
	 * Given a binary tree, find its minimum depth.
	 * The minimum depth is the number of nodes along 
	 * the shortest path from the root node down to the nearest leaf node.
	 * 
	 * root height = min(root.left, root.right) + 1
	 * @param root
	 * @return
	 */
	public static int minimumDepthOfBT(BTNode root){
		if(root == null) return 0;
		if(root.left == null && root.right == null) return 1; //a leaf
		int height1 = minimumDepthOfBT(root.left);
		int height2 = minimumDepthOfBT(root.right);
		return 1 + (height1 > height2 ? height2 : height1); 
	}
	
	/**
	 * Given a binary tree and a sum, 
	 * determine if the tree has a root-to-leaf path 
	 * such that adding up all the values along the path equals the given sum.
	 * @param root
	 * @param target
	 * @return
	 */
	public static boolean pathSum(BTNode root, int target){
		if(root == null && target ==  0) return true;
		else if(root == null && target != 0) return false;
		
		int newtarget = target - (int)root.val.doubleValue();
		if(pathSum(root.left, newtarget)) return true;
		else if(pathSum(root.right, newtarget)) return true;
		else return false;
	}
	
	/**
	 * 
	 * Given a binary tree and a sum, find all root-to-leaf paths 
	 * where each path's sum equals the given sum.
	 * @param root
	 * @param target
	 * @param path
	 * @param res
	 */
	public static void pathSumII(BTNode root, int target, List<BTNode> path , List<List<BTNode>> res){
		if(root == null) {
			if(target == 0) res.add(path);
			return;	
		}
		int newtarget = target - (int)root.val.doubleValue();
		List<BTNode> leftPath = new ArrayList<BTNode>();
		List<BTNode> rightPath = new ArrayList<BTNode>();
		leftPath.addAll(path);
		rightPath.addAll(path);
		leftPath.add(root);
		rightPath.add(root);
		pathSumII(root.left, newtarget, leftPath, res);
		pathSumII(root.right, newtarget, rightPath, res);
	}
	
	/**
	 * ! Given a binary tree, flatten it to a linked list in-place.
	 * For example,
	 * Given

         1
        / \
       2   5
      / \   \
     3   4   6
     * The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
       
       (Notice: in pre-order)
	 * @param root
	 * @param ind: the tail of the linked list
	 */
	public static void flattenBTToLinkedList(BTNode root, BTNode[] ind){
		if(root == null) return;
		if(root.left != null) {
			ind[0] = root.left;
			flattenBTToLinkedList(root.left, ind);
		}
		if(root.right != null){
			ind[0].left = root.right;//add node to the tail of this linkedlist
			ind[0] = ind[0].left;//renew tail
			flattenBTToLinkedList(root.right, ind);
			root.right = null;//notice, should do this
		}
	}
	
	/**
	 * ! Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
    Populate each next pointer to point to its next right node. 
    If there is no next right node, the next pointer should be set to NULL.
    Initially, all next pointers are set to NULL.
    Note:

	You may only use constant extra space.
	You may assume that it is a perfect binary tree 
	(ie, all leaves are at the same level, and every parent has two children).
	For example,
	Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7
	After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL
	 * @param root
	 */
	public static void populatingNextRightPointersInEachNode(TreeLinkNode root){
		
	}
	
	/**
	 * Follow up for problem "Populating Next Right Pointers in Each Node".
	 * What if the given tree could be any binary tree? Would your previous solution still work?
	 * Note:
	 * You may only use constant extra space.
	 * @param root
	 */
	public static void populatingNextRightPointersInEachNodeII(TreeLinkNode root){
		if(root == null) return;
		Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
		q.add(new TreeLinkNode(null));
		q.add(root);
		
		TreeLinkNode pre = null;
		TreeLinkNode node = null;
		while(!q.isEmpty()){
			node = q.poll();
			if(node.val == null && !q.isEmpty()){//new level
				if(pre != null)
					pre.next = null;
				pre = q.poll();
				q.add(new TreeLinkNode(null));
				if(pre.left != null) q.add((TreeLinkNode) pre.left);
				if(pre.right != null) q.add((TreeLinkNode) pre.right);
			}else{
				pre.next = node;
				pre = node;
				if(pre.left != null) q.add((TreeLinkNode) pre.left);
				if(pre.right != null) q.add((TreeLinkNode) pre.right);
			}
		}	
	}
	
	public static TreeLinkNode constructBSTFromSortedArray(int[] a, int start, int end){
		if(start > end) return null;
		int mid = start + (end - start)/2;
		TreeLinkNode root = new TreeLinkNode(a[mid]);
		root.left = constructBSTFromSortedArray(a, start, mid-1);
		root.right = constructBSTFromSortedArray(a, mid+1, end);
		return root;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BTNode root = LeetCode_day11_tree.constructBSTFromSortedArray(new int[]{1,2,3,4,5,6,7,8}, 0, 7);
		binaryTreeLevelOrderTraversalII(root);
		LinkedList<Integer> list = new LinkedList<Integer>();
		Integer[] temp = new Integer[]{1,2,3,4,5,6,7,8};
		list.addAll(Arrays.asList(temp));
		//BTNode root1 = convertSortedLinkedListToBalancedBST(list.iterator());
		zigzagLevelOrderTraversalBT(root);
		
		System.out.println(balancedBT(root));
		System.out.println("**");
		flattenBTToLinkedList(root, new BTNode[]{root});
		binaryTreeLevelOrderTraversalII(root);
		TreeLinkNode newroot = constructBSTFromSortedArray(new int[]{1,2,3,4,5,6,7,8}, 0, 7);
		populatingNextRightPointersInEachNodeII(newroot);
		System.out.println("**");
	}

}

class TreeLinkNode<T extends Number> extends BTNode{
	TreeLinkNode next;
	public TreeLinkNode(T val){
		super(val);
	}
}
